package developer.算法.二分查找.搜索二维矩阵;

/**
 * @author zhangyongkang
 * @time 2025/4/2 11:48
 * @description 给你一个满足下述两条属性的 m x n 整数矩阵：
 * <p>
 * 每行中的整数从左到右按非严格递增顺序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 */
public class SouSuoErWeiJvZhen {

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        int[][] matrix = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}
        };

        System.out.println(solution.searchMatrix(matrix, 3));
        System.out.println(solution.searchMatrix(matrix, 13));
        System.out.println(solution.searchMatrix(new int[][]{{1}}, 2));
    }

    static class Solution4 {
        public boolean searchMatrix(int[][] matrix, int target) {
            int left = 0, right = matrix.length * matrix[0].length - 1;

            while (left <= right) {
                int midIdx = left + (right - left) / 2;
                int midVal = matrix[midIdx / matrix[0].length][midIdx % matrix[0].length];
                if (target == midVal) {
                    return true;
                }
                if (midVal > target) {
                    right = midIdx - 1;
                } else {
                    left = midIdx + 1;
                }
            }
            return false;
        }
    }

    static class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int l = 0, r = matrix.length * matrix[0].length - 1;
            while (l <= r) {
                int mid = (r - l) / 2 + l;
                //这里是核心-> 将多个矩阵看作一个数组
                int midVal = matrix[mid / matrix[0].length][mid % matrix[0].length];
                if (target > midVal) {
                    l = mid + 1;
                } else if (target < midVal) {
                    r = mid - 1;
                } else {
                    return true;
                }
            }
            return false;
        }
    }

}
